package com.fw.leetcode.linkedlist;

import com.fw.leetcode.LeetCode;

/**
 * 206. Reverse Linked List
 *
 * Given the head of a singly linked list, reverse the list, and return the reversed list.
 *
 * Example 1:
 *  Input: head = [1,2,3,4,5]
 *  Output: [5,4,3,2,1]
 *
 * Example 2:
 *  Input: head = [1,2]
 *  Output: [2,1]
 *
 * Example 3:
 *  Input: head = []
 *  Output: []
 *
 * Constraints:
 *  The number of nodes in the list is the range [0, 5000].
 *  -5000 <= Node.val <= 5000
 *
 * Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
 */
public class Num_0206 implements LeetCode {
    private interface Solution extends LinkedList {
        ListNode reverseList(ListNode head);

        default void assertExpected(int[] head, int[] expected) {
            if (!assertEquals(reverseList(build(head)), build(expected))) {
                reverseList(build(head));
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public ListNode reverseList(ListNode head) { // 最优：时O(n) 空O(1)
            /*
             * 反转链表（新建链表，原头出，新头进）
             * head -> [1,2,3]
             * reverse -> []
             *
             * head -> [2,3]
             * reverse -> [1]
             *
             * head -> [3]
             * reverse -> [2,1]
             *
             * head -> []
             * reverse -> [3,2,1]
             */
            ListNode header = new ListNode(-1);
            ListNode cur = head;
            ListNode curNext;
            while (cur != null) {
                curNext = cur.next;
                // 插入
                cur.next = header.next;
                header.next = cur;
                // 后移
                cur = curNext;
            }
            return header.next;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MySolution();
        solution.assertExpected(new int[]{}, new int[]{});
        solution.assertExpected(new int[]{1}, new int[]{1});
        solution.assertExpected(new int[]{1,2}, new int[]{2,1});
        solution.assertExpected(new int[]{1,2,3}, new int[]{3,2,1});
        solution.assertExpected(new int[]{1,2,3,4}, new int[]{4,3,2,1});
        solution.assertExpected(new int[]{1,2,3,4,5}, new int[]{5,4,3,2,1});
    }
}
